#define _CRT_SECURE_NO_WARNINGS 1

//DFS
//class Solution {
//public:
//    bool isPass(vector<vector<char>>& grid, int x, int y, int row, int col) {
//        if (x >= 0 && x < row
//            && y >= 0 && y < col
//            && grid[x][y] == '1')
//            return true;
//        else
//            return false;
//    }
//
//    void DFS(vector<vector<char>>& grid, int x, int y, int row, int col) {
//        grid[x][y] = '0';
//        if (isPass(grid, x - 1, y, row, col)) DFS(grid, x - 1, y, row, col);
//        if (isPass(grid, x + 1, y, row, col)) DFS(grid, x + 1, y, row, col);
//        if (isPass(grid, x, y - 1, row, col)) DFS(grid, x, y - 1, row, col);
//        if (isPass(grid, x, y + 1, row, col)) DFS(grid, x, y + 1, row, col);
//    }
//
//    int numIslands(vector<vector<char>>& grid) {
//        int ans = 0;
//        int row = grid.size();
//        int col = grid[0].size();
//        for (int i = 0; i < row; i++)
//            for (int j = 0; j < col; j++)
//                if (grid[i][j] == '1') {
//                    ans++;
//                    DFS(grid, i, j, row, col);
//                }
//        return ans;
//    }
//};


//BFS
//class Solution {
//public:
//    bool isPass(vector<vector<char>>& grid, int x, int y, int row, int col) {
//        if (x >= 0 && x < row
//            && y >= 0 && y < col
//            && grid[x][y] == '1')
//            return true;
//        else
//            return false;
//    }
//
//    void BFS(vector<vector<char>>& grid, int x, int y, int row, int col) {
//        queue<pair<int, int>> qu;
//        qu.push(pair<int, int>(x, y));
//        while (!qu.empty()) {
//            int Front_x = qu.front().first;
//            int Front_y = qu.front().second;
//            qu.pop();
//            if (isPass(grid, Front_x - 1, Front_y, row, col)) {
//                qu.push({ Front_x - 1, Front_y });
//                grid[Front_x - 1][Front_y] = '0';
//            }
//            if (isPass(grid, Front_x + 1, Front_y, row, col)) {
//                qu.push({ Front_x + 1, Front_y });
//                grid[Front_x + 1][Front_y] = '0';
//            }
//            if (isPass(grid, Front_x, Front_y - 1, row, col)) {
//                qu.push({ Front_x, Front_y - 1 });
//                grid[Front_x][Front_y - 1] = '0';
//            }
//            if (isPass(grid, Front_x, Front_y + 1, row, col)) {
//                qu.push({ Front_x, Front_y + 1 });
//                grid[Front_x][Front_y + 1] = '0';
//            }
//        }
//    }
//
//    int numIslands(vector<vector<char>>& grid) {
//        int ans = 0;
//        int row = grid.size();
//        int col = grid[0].size();
//        for (int i = 0; i < row; i++)
//            for (int j = 0; j < col; j++)
//                if (grid[i][j] == '1') {
//                    ans++;
//                    BFS(grid, i, j, row, col);
//                }
//        return ans;
//    }
//};